191 - Intersection/191.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <sstream>
   6 #include <fstream>
   7 #include <cassert>
   8 #include <climits>
   9 #include <cstdlib>
  10 #include <cstring>
  11 #include <string>
  12 #include <cstdio>
  13 #include <vector>
  14 #include <cmath>
  15 #include <queue>
  16 #include <deque>
  17 #include <stack>
  18 #include <list>
  19 #include <map>
  20 #include <set>
  21
  22 #define D(x) cout << #x " is " << x << endl
  23
  24
  25 /*
  26   Returns true if point (x, y) lies inside (or in the border)
  27   of box defined by points (x0, y0) and (x1, y1).
  28 */
  29 bool point_in_box(double x, double y,
  30                   double x0, double y0,    double x1, double y1){
  31   return min(x0, x1) <= x && x <= max(x0, x1) && min(y0, y1) <= y && y <= max(y0, y1);
  32 }
  33
  34 /*
  35   Finds the intersection between two segments (Not infinite lines!)
  36   Segment 1 goes from point (x0, y0) to (x1, y1).
  37   Segment 2 goes from point (x2, y2) to (x3, y3).
  38
  39   Handles the case when the 2 segments are:
  40   *Parallel but don't lie on the same line (No intersection)
  41   *Parallel and both lie on the same line (Infinite intersections or no intersections)
  42   *Not parallel (One intersection or no intersections)
  43
  44   Returns true if the segments do intersect in any case.
  45 */
  46 bool segment_segment_intersection(double x0, double y0,   double x1, double y1,
  47                                   double x2, double y2,   double x3, double y3){
  48 #ifndef EPS
  49 #define EPS 1e-9
  50 #endif
  51
  52   double t0 = (y3-y2)*(x0-x2)-(x3-x2)*(y0-y2);
  53   double t1 = (x1-x0)*(y2-y0)-(y1-y0)*(x2-x0);
  54   double det = (y1-y0)*(x3-x2)-(y3-y2)*(x1-x0);
  55   if (fabs(det) < EPS){
  56     //parallel
  57     if (fabs(t0) < EPS || fabs(t1) < EPS){
  58       //they lie on same line, but they may or may not intersect.
  59       return (point_in_box(x0, y0,   x2, y2, x3, y3) ||
  60               point_in_box(x1, y1,   x2, y2, x3, y3) ||
  61               point_in_box(x2, y2,   x0, y0, x1, y1) ||
  62               point_in_box(x3, y3,   x0, y0, x1, y1));
  63     }else{
  64       //just parallel, no intersection
  65       return false;
  66     }
  67   }else{
  68     t0 /= det;
  69     t1 /= det;
  70     /*
  71       0 <= t0 <= 1 if the intersection point lies in segment 1.
  72       0 <= t1 <= 1 if the intersection point lies in segment 2.
  73     */
  74     if (0.0 <= t0 && t0 <= 1.0 && 0.0 <= t1 && t1 <= 1.0){
  75       double x = x0 + t0*(x1-x0);
  76       double y = y0 + t0*(y1-y0);
  77       //intersection is point (x, y)
  78       return true;
  79     }
  80     //the intersection points doesn't lie on both segments.
  81     return false;
  82   }
  83 }
  84
  85 typedef pair<double, double> point;
  86 typedef pair<point, point> segment;
  87
  88 bool point_in_box(point x, point a, point b){
  89   return point_in_box(x.first, x.second, a.first, a.second, b.first, b.second);
  90 }
  91
  92 bool segment_segment_intersection(segment a, segment b){
  93   return segment_segment_intersection(a.first.first, a.first.second,
  94                                       a.second.first, a.second.second,
  95                                       b.first.first, b.first.second,
  96                                       b.second.first, b.second.second);
  97 }
  98
  99
 100 int main(){
 101   int n;
 102   scanf("%d", &n);
 103   while (n--){
 104     double x0, y0, x1, y1, x2, y2, x3, y3;
 105     scanf("%lf %lf %lf %lf %lf %lf %lf %lf",
 106           &x0, &y0, &x1, &y1, &x2, &y2, &x3, &y3);
 107     bool boom =
 108       point_in_box(x0, y0, x2, y2, x3, y3) ||
 109       point_in_box(x1, y1, x2, y2, x3, y3);
 110
 111     point a, b, c, d;
 112     a = point(x2, y2);
 113     b = point(x2, y3);
 114     c = point(x3, y2);
 115     d = point(x3, y3);
 116
 117     segment line = segment(point(x0, y0), point(x1, y1));
 118     boom |=
 119       segment_segment_intersection(line, segment(a, b)) ||
 120       segment_segment_intersection(line, segment(a, c)) ||
 121       segment_segment_intersection(line, segment(b, d)) ||
 122       segment_segment_intersection(line, segment(c, d));
 123
 124     printf("%s\n", (boom ? "T" : "F"));
 125
 126   }
 127   return 0;
 128 }